package com.yoshino.leetcode.oneHundred.threetyfirst;

class Solution {
    public int cuttingRope(int n) {
        if (n < 4) {
            return n - 1;
        }
        // 拆为 3 及 2
        long res = 1;
        while (n > 4) {
            res = (res * 3 % 1000000007);
            n -= 3;
        }
        return (int)(res * n % 1000000007);
    }
}